/*
 * Project: BoboDesignPattern
 * 
 * File Created at 2020年2月21日
 * 
 * Copyright 2012 Greenline.com Corporation Limited.
 * All rights reserved.
 *
 * This software is the confidential and proprietary information of
 * Greenline Company. ("Confidential Information").  You shall not
 * disclose such Confidential Information and shall use it only in
 * accordance with the terms of the license agreement you entered into
 * with Greenline.com.
 */
package test.practice;

import java.util.Arrays;

/**
 * @Type A20200221_sorttest
 * @Desc
 * @author 52489
 * @date 2020年2月21日
 * @Version V1.0
 */
public class A20200222_meragesort {
    public static void main(String[] args) {
        int[] nums = { 10, 6, 3, 8, 33, 27, 66, 9, 7, 88, 20 };
        int start = 0;
        int end = nums.length - 1;
        sort(nums, start, end);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * @param nums
     * @return
     */
    private static void sort(int[] nums, int start, int end) {
        if (nums == null || start >= end) {
            return;
        }
        int mid = start + (end - start) / 2;
        sort(nums, start, mid);
        sort(nums, mid + 1, end);
        merage(nums, start, mid, end);
    }

    /**
     * @param nums
     * @param start
     * @param mid
     * @param end
     */
    private static void merage(int[] nums, int start, int mid, int end) {
        int tmp[] = new int[end - start + 1];
        int i = start;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= end) {
            if (nums[i] < nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
            }
        }

        while (i <= mid) {
            tmp[k++] = nums[i++];

        }

        while (j <= end) {
            tmp[k++] = nums[j++];
        }

        for (i = 0; i < tmp.length; i++) {
            nums[start + i] = tmp[i];
        }

        tmp = null;

    }
}
